// https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0];
        }
        
        int count = 0, h = nums.size() / 2;
        unordered_map<int, int> mp;
        for (int i = 0; i < nums.size(); i++) {
            if (mp.count(nums[i]) < 1) {
                mp.insert(make_pair(nums[i], 1));
            } else {
                mp[nums[i]]++;
                if (mp[nums[i]] > h) {
                    return nums[i];
                }
            }
        }
        return 0;
    }
};